package Recursive_search_backtracking_algorithm.Topic1_recursive_algorithm.Topic1_recursive_algorithm;

import java.util.List;

public class Topic1_recursive_algorithm {
    // blog : 【递归，搜索与回溯算法 & 递归算法】递归算法入门详解：递归算法小专题
    //https://blog.csdn.net/2402_84916296/article/details/144481329?spm=1001.2014.3001.5501


    //面试题08.06.汉诺塔问题
    //https://leetcode.cn/problems/hanota-lcci/
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs( A, B, C, A.size());
    }
    public void dfs (List<Integer> A, List<Integer> B, List<Integer> C,int n){
        if(n==1){
            C.add(A.remove(A.size()-1));
            return;
        }
        dfs(A,C,B,n-1);
        C.add(A.remove(A.size()-1));
        dfs(B,A,C,n-1);
    }


    //21.合并两个有序链表
    //https://leetcode.cn/problems/merge-two-sorted-lists/description/

    public class ListNode {
        int val;
        Topic1_recursive_algorithm.ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, Topic1_recursive_algorithm.ListNode next) { this.val = val; this.next = next; }
    }

    public Topic1_recursive_algorithm.ListNode mergeTwoLists(Topic1_recursive_algorithm.ListNode list1, Topic1_recursive_algorithm.ListNode list2) {
        if(list1==null ){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //递归出口理解不到位
        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
        }else{
            list2.next = mergeTwoLists(list1,list2.next);
        }
        return list1.val < list2.val ? list1 : list2;
    }


    //206. 反转链表
    //https://leetcode.cn/problems/reverse-linked-list/

    public Topic1_recursive_algorithm.ListNode reverseList(Topic1_recursive_algorithm.ListNode head) {
        if(head==null || head.next == null){
            return head;
        }
        Topic1_recursive_algorithm.ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    //24. 两两交换链表中的节点
    //https://leetcode.cn/problems/swap-nodes-in-pairs/description/
    public Topic1_recursive_algorithm.ListNode swapPairs(Topic1_recursive_algorithm.ListNode head) {
        if(head==null||head.next==null){  //没有节点或者只剩一个节点，就不需要交换，直接返回（易错点一）
            return head;
        }
        //牢记 dfs() 的任务：1. 把第三个节点之后的链表节点两两交换；2. 返回交换后的头节点(这两点自己想都不好想，尤其是第二点)

        Topic1_recursive_algorithm.ListNode tmp = swapPairs(head.next.next);  //先用 dfs 交换除前面两个节点之外的其他节点，也就是第三个节点（易错点二）

        Topic1_recursive_algorithm.ListNode ret = head.next;    //需要记录原链表的第二个节点作为返回值（易错点三）

        ret.next=head;   //子问题：交换两个节点，并且拿交换部分和经过 dfs 得到的链表头节点连接

        head.next=tmp;

        return ret;   //原链表第二个节点
    }


    //50.Pow(x,n)
    //https://leetcode.cn/problems/powx-n/

    public double myPow(double x, int n) {
        double tmp = 1.0; //

        if (n < 0) {

            for (int i = 0; i < -n; i++) {
                tmp *= x;
            }

            return 1.0 / tmp;

        } else {

            for (int i = 0; i < n; i++) {
                tmp *= x;
            }

            return tmp;
        }
    }
}
